package com.company.algo.tree;

/**
 * 116. 填充每个节点的下一个右侧节点指针
 * 题目说明了给出的树是一颗完美二叉树
 */

class Node{
    int val;
    Node left;
    Node right;
    Node next;
}
public class Connect {
    public Node connect(Node root) {
        if (root == null) return null;
        connectTwoNodes(root.left,root.right);
        return root;
    }

    private void connectTwoNodes(Node node1, Node node2) {
        if (node1 == null || node2 == null) return;
        // 将传入的两个节点连接
        node1.next = node2;
        // 连接相同父节点的两个子节点
        connectTwoNodes(node1.left,node1.right);
        connectTwoNodes(node2.left,node2.right);
        // 连接跨越父节点的两个子节点
        connectTwoNodes(node1.right,node2.left);
    }
}

